package com.datastructure.sort;

public class InsertSort {

    public static void main(String[] args) {

    }

    public static void insertSort(int [] arr){
        for(int i = 1; i < arr.length;i++){
            int insertVal = arr[i];
            int insertIndex = i - 1; // 表示有序表最后这个元素的下标
            // 还没找到位置
            while(insertIndex >= 0 && insertVal < arr[insertIndex]){
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex -= 1;
            }
            // 退出while循环，说明插入的位置找到了
            if(insertIndex + 1 != i){
                arr[insertIndex + 1] = insertVal;
            }
        }
    }


}
